package array;

/*
 * Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
 * You may assume no duplicates in the array.
 * Here are few examples.
 * [1,3,5,6], 5 -> 2
 * [1,3,5,6], 2 -> 1
 * [1,3,5,6], 7 -> 4
 * [1,3,5,6], 0 -> 0
 */
public class SearchInsertPosition {

	public static int search(int[] a, int key) {
		int low = 0, high = a.length - 1;
		while (low <= high) {
			int mid = low + (high - low) / 2;
			if (a[mid] == key)
				return mid;
			else if (a[mid] > key)
				high = mid - 1;
			else
				low = mid + 1;
		}
		return low;
	}

	public static void main(String[] args) {
		int[] a = new int[] { 1, 3, 5, 6, 8 };
		for (int i = 0; i < 10; i++) {
			System.out.println(i + ": " + search(a, i));
		}
	}

}
